// 回溯算法
var partition = function (s) {
  let res = [];
  const backtrack = (start, path, res) => {
    if (start === s.length) {
      res.push(path);
      return;
    }
    for (let i = start; i < s.length; i++) {
      if (!isPalindrome(start, i)) continue;
      path.push(s.slice(start, i + 1));
      backtrack(i + 1, path.slice(), res);
      path.pop();
    }
  };
  backtrack(0, [], res);
  return res;

  function isPalindrome(left, right) {
    while (left < right) {
      if (s[left++] !== s[right--]) return false;
    }
    return true;
  }
};
